/*
 * TestFul - http://code.google.com/p/testful/
 * Copyright (C) 2010  Matteo Miraz
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package testful.evolutionary;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.logging.Logger;

import jmetal.base.Algorithm;
import jmetal.base.Problem;
import jmetal.base.Solution;
import jmetal.base.SolutionSet;
import jmetal.base.TerminationCriterion;
import jmetal.base.Variable;
import jmetal.base.operator.crossover.Crossover;
import jmetal.base.operator.localSearch.LocalSearch;
import jmetal.base.operator.localSearch.LocalSearchPopulation;
import jmetal.base.operator.mutation.Mutation;
import jmetal.base.operator.selection.Selection;
import jmetal.util.Distance;
import jmetal.util.JMException;
import jmetal.util.PseudoRandom;
import testful.IUpdate;
import testful.evolutionary.IConfigEvolutionary.FitnessInheritance;

/**
 * This class implements the NSGA-II algorithm. Adapted from JMetal.
 */
public class NSGAII<V extends Variable>
extends
Algorithm<V, Crossover<V>, Mutation<V>, Selection<V, Solution<V>>, LocalSearch<V>>
implements IUpdate {

	private static final Logger logger = Logger
			.getLogger("testful.evolutionary");

	private static final long serialVersionUID = 4970928169851043408L;

	private List<Callback> callbacks = new LinkedList<Callback>();

	@Override
	public void register(Callback c) {
		this.callbacks.add(c);
	}

	@Override
	public void unregister(Callback c) {
		this.callbacks.remove(c);
	}

	private void update(TerminationCriterion criterion) {
		for (Callback c : callbacks)
			c.update(criterion);
	}

	/** stores the problem to solve */
	private Problem<V> problem_;

				/** probability to inherit the fitness */
				private final float INHERIT_PROBABILITY = 0.55f;

				/** is fitness inheritance enabled */
				private FitnessInheritance inherit = FitnessInheritance.DISABLED;

				/** period of the local search (in generations) */
				private int localSearchPeriod = 20;

				/** number of elements on which the local search is applied */
				private int localSearchNum = 0;

				/**
				 * Constructor
				 * 
				 * @param problem
				 *            Problem to solve
				 */
				public NSGAII(Problem<V> problem) {
					this.problem_ = problem;
				} // NSGAII

				public void setInherit(FitnessInheritance inherit) {
					this.inherit = inherit;
				}

				public FitnessInheritance getInherit() {
					return inherit;
				}

				public void setLocalSearchPeriod(int localSearchPeriod) {
					this.localSearchPeriod = localSearchPeriod;
				}

				public int getLocalSearchPeriod() {
					return localSearchPeriod;
				}

				public void setLocalSearchNum(int localSearchNum) {
					this.localSearchNum = localSearchNum;
				}

				public void setLocalSearchNum(float perc) {
					if (perc < 0)
						perc = 0;
					if (perc > 1)
						perc = 1;

					this.localSearchNum = (int) (getPopulationSize() * perc);
				}

				public int getLocalSearchNum() {
					return localSearchNum;
				}

				/**
				 * Runs the NSGA-II algorithm.
				 * 
				 * @return a <code>SolutionSet</code> that is a set of non dominated
				 *         solutions as a result of the algorithm execution
				 * @throws JMException
				 *             if something goes wrong
				 */
				@Override
				public SolutionSet<V> execute() throws JMException {
					SolutionSet<V> population;
					SolutionSet<V> union;

					// Read the parameters
					final int populationSize = getPopulationSize();

					// Initialize the variables
					population = new SolutionSet<V>(populationSize);

					int currentGeneration = 0;
					problem_.setCurrentGeneration(currentGeneration, 0);

					// Create the initial solutionSet
					logger.info(String.format(
							"(%5.2f%%) Creating initial population - %s to go",
							getTerminationCriterion().getProgressPercent(),
							getTerminationCriterion().getRemaining()));
					for (int i = 0; i < populationSize; i++) {
						// Solution<V> tmp = new Solution<V>(problem_);
						// population.add(tmp);

						PSOSolution<V> tmp2 = new PSOSolution<V>(problem_);
						population.add(tmp2);
						// testful.evolutionary.Launcher.txtLog.logs.append(tmp2.getSwapOp()
						// .toString());

						// List<V> list = tmp.getDecisionVariables().variables_;
						// testful.evolutionary.Launcher.txtLog.logs.append("############# show individuals ###############\n");
						// for (V v : list) {
						// Operation o = (Operation) v;
						// testful.evolutionary.Launcher.txtLog.logs.append("###:"+
						// o.toString() + "\n");
						// }
						// testful.evolutionary.Launcher.txtLog.logs.append("############# show individuals end ###############\n");
						//
						// List<V> list2 = tmp2.getDecisionVariables().variables_;
						// testful.evolutionary.Launcher.txtLog.logs.append("############# show individuals 2###############\n");
						// for (V v : list2) {
						// Operation o = (Operation) v;
						// testful.evolutionary.Launcher.txtLog.logs.append("###:"+
						// o.toString() + "\n");
						// }
						// testful.evolutionary.Launcher.txtLog.logs.append("############# show individuals2 end ###############\n");
						// SwapUtil.applyChange(tmp2, tmp2.getSwapOp());
						//
						// List<V> list3 = tmp2.getDecisionVariables().variables_;
						// testful.evolutionary.Launcher.txtLog.logs.append("############# show individuals 3###############\n");
						// for (V v : list3) {
						// Operation o = (Operation) v;
						// testful.evolutionary.Launcher.txtLog.logs.append("###:"+
						// o.toString() + "\n");
						// }
						// testful.evolutionary.Launcher.txtLog.logs.append("############# show individuals2 end ###############\n");
						// testful.evolutionary.Launcher.txtLog.logs.append(SwapUtil.getSwapOperation(list2,
						// list).toString());

					}

					// Evaluating initial population
					logger.info(String.format(
							"(%5.2f%%) Generation 0 (initial population) - %s to go",
							getTerminationCriterion().getProgressPercent(),
							getTerminationCriterion().getRemaining()));

					for (Solution<V> solution : population) {
						problem_.evaluateConstraints(solution);
					}

					// Generations ...
					while (!getTerminationCriterion().isTerminated()) {
						problem_.setCurrentGeneration(++currentGeneration,
								getTerminationCriterion().getProgress());
						// update the termination criterion
						update(getTerminationCriterion());

						logger.info(String
								.format("(%5.2f%%) Generation %d - %s to go",
										getTerminationCriterion().getProgressPercent(),
										currentGeneration, getTerminationCriterion()
										.getRemaining()));

						// perform the improvement
						if (improvement != null
								&& currentGeneration % localSearchPeriod == 0) {

							if (localSearchNum == 0
									&& improvement instanceof LocalSearchPopulation<?>) {
								SolutionSet<V> front = Ranking.getFrontier(population);
								logger.info("Local search on fronteer (" + front.size()
										+ ")");
								SolutionSet<V> mutated = ((LocalSearchPopulation<V>) improvement)
										.execute(front);
								if (mutated != null)
									problem_.evaluate(mutated);
							} else {
								for (int i = 0; i < localSearchNum
										&& !getTerminationCriterion().isTerminated(); i++) {
									final int randInt = PseudoRandom
											.getMersenneTwisterFast().nextInt(
													populationSize);
									logger.info("Local search " + i + "/" + localSearchNum
											+ " on element " + randInt);
									Solution<V> solution = population.get(randInt);
									solution = improvement.execute(solution);
									if (solution != null) {
										problem_.evaluate(solution);
									}
								}
							}
							continue;
						}

						// Solution<Binary> parent_tmp = (Solution<Binary>)population;

						// Create the offSpring solutionSet
						SolutionSet<V> offspringPopulation = new SolutionSet<V>(
								populationSize);
						for (int i = 0; i < (populationSize / 2); i++) {
							// obtain parents
							Solution<V> parent1 = selectionOperator.execute(population);
							Solution<V> parent2 = selectionOperator.execute(population);
							Solution<V>[] offSpring = crossoverOperator.execute(parent1,
									parent2);
							mutationOperator.execute(offSpring[0]);
							mutationOperator.execute(offSpring[1]);
							offspringPopulation.add(offSpring[0]);
							offspringPopulation.add(offSpring[1]);
						}

						// select individuals to evaluate
						Iterable<Solution<V>> toEval = offspringPopulation;

						switch (inherit) {
						// in this project use UNIFORM
						case UNIFORM:
							List<Solution<V>> tmpu = new ArrayList<Solution<V>>();
							for (Solution<V> s : offspringPopulation)
								if (!PseudoRandom.getMersenneTwisterFast().nextBoolean(
										INHERIT_PROBABILITY))
									tmpu.add(s);

									toEval = tmpu;
									break;

						case FRONTEER:
							List<Solution<V>> tmpf = new ArrayList<Solution<V>>();

							final Ranking<V> ranking = new Ranking<V>(population);
							final SolutionSet<V> fronteer = ranking.next();
							final List<Solution<V>> others = new ArrayList<Solution<V>>();

							while (ranking.hasNext()) {
								for (Solution<V> s : ranking.next()) {
									others.add(s);
								}
							}

							final int n = offspringPopulation.size();
							final int f = fronteer.size();

							final float k = 0.5f;
							final float pf = k * INHERIT_PROBABILITY * n
									/ (n + f * (k - 1.0f));
							final float po = (pf / k) >= 1 ? 1 : pf / k;

							for (Solution<V> s : fronteer) {
								if (!PseudoRandom.getMersenneTwisterFast().nextBoolean(pf)) {
									tmpf.add(s);
								}
							}

							for (Solution<V> s : others) {
								if (!PseudoRandom.getMersenneTwisterFast().nextBoolean(po)) {
									tmpf.add(s);
								}
							}

							toEval = tmpf;
							break;
						}

						// evaluate individuals
						problem_.evaluate(toEval);
						for (Solution<V> solution : toEval) {
							problem_.evaluateConstraints(solution);
						}

						// Create the solutionSet union of solutionSet and offSpring
						union = population.union(offspringPopulation);

						// Ranking the union
						Ranking<V> ranking = new Ranking<V>(union);

						int remain = populationSize;
						SolutionSet<V> front = null;
						population.clear();

						// Obtain the next front
						front = ranking.next();

						while ((remain > 0) && (remain >= front.size())) {
							// Assign crowding distance to individuals
							Distance.crowdingDistanceAssignment(front,
									problem_.getNumberOfObjectives());
							// Add the individuals of this front
							for (Solution<V> s : front){
								population.add(s);
							}

							// Decrement remain
							remain = remain - front.size();

							// Obtain the next front
							if (remain > 0) {
								front = ranking.next();
							}
						} // while

						// Remain is less than front(index).size, insert only the best one
						if (remain > 0) { // front contains individuals to insert
							Distance.crowdingDistanceAssignment(front,
									problem_.getNumberOfObjectives());
							front.sort(new jmetal.base.operator.comparator.CrowdingComparator<V>());
							for (int k = 0; k < remain; k++) {
								population.add(front.get(k));
							}

							remain = 0;
						} // if

					} // while

					// Return the first non-dominated front
					SolutionSet<V> result = Ranking.getFrontier(population);

					return result;
				} // execute
} // NSGA-II
